1. 题目描述（简单难度）

[success] 572. 另一个树的子树

解法一： 深度优先暴力匹配

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
      //s遍历完成，还没匹配到
      if(root == null){
          return false;
      }
      //短路，左子树或者右子树有匹配到的就返回
      return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }


    //100题判断是否是同一颗树
    public boolean isSameTree(TreeNode root,TreeNode subRoot){
        if(root == null && subRoot == null){
            return true;
        }
        if(root == null || subRoot == null){
            return false;
        }
        if(root.val != subRoot.val){
            return false;
        }
        return isSameTree(root.left,subRoot.left) && isSameTree(root.right,subRoot.right);
    }
}

解法二：迭代

List保存每个树节点，取每个树节点进行判断是否与子树相等

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
       List<TreeNode> list = new ArrayList<>();
       preOrderQueue(root,list);

       StringBuilder sb = new StringBuilder();
       preOrder(subRoot,sb);

       for(int i=0;i<list.size();i++){
           StringBuilder sb1 = new StringBuilder();
           TreeNode node = list.get(i);
           preOrder(node,sb1);
           if(sb.toString().equals(sb1.toString())){
               return true;
           }
       }
       return false;
    }

    public void preOrder(TreeNode root,StringBuilder sb){
        if(root == null){
            sb.append("-1");
            return;
        }
        sb.append(root.val);
        preOrder(root.left,sb);
        preOrder(root.right,sb);
    }

    public void preOrderQueue(TreeNode root,List<TreeNode> list){
        if(root == null){
            return;
        }
        list.add(root);
        preOrderQueue(root.left,list);
        preOrderQueue(root.right,list);
    }
}

使用递归判断子树是否相同

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
       List<TreeNode> list = new ArrayList<>();
       preOrderQueue(root,list);
       for(int i=0;i<list.size();i++){
          if(isSameTree(list.get(i),subRoot)){
              return true;
          }
       }
       return false;
    }

    public void preOrderQueue(TreeNode root,List<TreeNode> list){
        if(root == null){
            return;
        }
        list.add(root);
        preOrderQueue(root.left,list);
        preOrderQueue(root.right,list);
    }

    public boolean isSameTree(TreeNode root,TreeNode subRoot){
        if(root == null && subRoot == null){
            return true;
        }
        if(root == null || subRoot == null){
            return false;
        }
        if(root.val != subRoot.val){
            return false;
        }
        return isSameTree(root.left,subRoot.left) && isSameTree(root.right,subRoot.right);
    }
}